#include "EaToFindRectangles.h"
#include <algorithm>
#include <numeric>
#include <assert.h>
#include <chrono>


using namespace std;

namespace EaHelpers
{
	long int indPenalty(const vector<Rectangle>& ind, const vector<Coordinate>& majors)
	{
		long int coveredMajors = 0;
		vector<Coordinate>::const_iterator cooIt = majors.begin();
		for (; cooIt!= majors.end(); ++cooIt)
		{
			vector<Rectangle>::const_iterator recIt = ind.begin();
			for (; recIt != ind.end(); ++recIt)
			{
				if (recIt->cooIsInside(*cooIt))
				{
					++coveredMajors;
				}
			}
		}

		//penalty0 = #of rectangles x (covered majors)^2 
		//penalty1 = #of rectangles (1 + (covered majors)^2 ) , to avoid penalty = 0;
		//result *= result;
		//result*= (long int) ind.size();
		//result+= (long int) ind.size();
		long int nonameFactor = (long int) sqrt((MROWS + MCOLS)/2);
		long int MajorsElement = /*1 + */((coveredMajors + nonameFactor) * (coveredMajors + nonameFactor));
		//return (long int) ind.size() * MajorsElement;
		return (long int) 2*ind.size() + MajorsElement;
	}

	bool weAreGettingBetter(const long int* bestPenaltyArray, int arraySize)
	{
		if (!bestPenaltyArray)
		{
			cerr << "\ninvalid bestPenaltyArray in checking the termination condition of EA.";
			exit(-1);
		}
		long int lastBest = bestPenaltyArray[0];
		for (int i = 1; i < arraySize; ++i)
		{
			if (lastBest != bestPenaltyArray[i])
			{
				return true;
			}
		}
		return false;
	}

	int bestIndIndexAmongCandidates(const vector<int>& candidateParentIndex, const vector<long int>& penalty)
	{
		assert (candidateParentIndex.size() < penalty.size() && "\nError in bestIndIndexAmongCandidates");
		int bestIndexSoFar = candidateParentIndex[0];
		long int bestPenaltySofar = penalty[candidateParentIndex[0]];
		for (int i = 1; i < static_cast<int>(candidateParentIndex.size()); ++i)
		{
			if (penalty[candidateParentIndex[i]] < bestPenaltySofar)
			{
				bestPenaltySofar = penalty[candidateParentIndex[i]];
				bestIndexSoFar = candidateParentIndex[i];
			}
		}
		return bestIndexSoFar;
	}

	/**
	 * eliteIndex[0] has the least penalty (the best individual).
	 * This function sorts the indices in eliteIndex from the least
	 * penalty to the highest.
	 */
	void sortEliteIndexVectorBasedOnPenalty(vector<int>& eliteIndex, vector<long int>& penalty)
	{
		int eliteNum = (int) eliteIndex.size();
		vector<int> originalIndex(eliteIndex);
		bool* isSelected = new bool[eliteNum];
		vector<long int> subPenalty; //to hold the penalties of the elites only
		subPenalty.reserve(eliteNum);
		for (int i = 0; i < eliteNum; ++i)
		{
			subPenalty.push_back(penalty[eliteIndex[i]]);
			isSelected[i] = false;
		}
		
		vector<long int> sortedSubPenalty(subPenalty);
		sort(sortedSubPenalty.begin(), sortedSubPenalty.end());

		for (int i = 0; i < eliteNum; ++i)
		{
			int locationInSubPenalty = 0;
			while (locationInSubPenalty < eliteNum)
			{
				if (sortedSubPenalty[i] == subPenalty[locationInSubPenalty] && !isSelected[locationInSubPenalty])
				{
					break;
				}
				++locationInSubPenalty;
			}

			if (locationInSubPenalty >= eliteNum)
			{
				cerr << "\nDid not find the matching value for the ranking operation.";
				assert (false && "Did not find the matching value for the ranking operation.");
			}

			isSelected[locationInSubPenalty] = true;
			eliteIndex[i] = originalIndex[locationInSubPenalty];
		}
		delete[] isSelected;
	}
}

EaToFindRectangles::EaToFindRectangles(LongInstance& majorLI, LongInstance& minorLI)
{
	if (minorLI.getCooNum() == 1)
	{
		cerr << "Why are you using a GA for a single coordinate???";
	}

	majors = majorLI.getCoordinateVector();
	minors = minorLI.getCoordinateVector();
		
	unsigned long seed = static_cast<unsigned long>(std::chrono::system_clock::now().time_since_epoch().count());
	randomLongGenerator = std::default_random_engine(seed);
	
	popSize = 0;
	maxGeneration = 0;
	childrenNum = 0;
	eliteNum = 0;
}

void EaToFindRectangles::setParameters ( int popsize, int generationNum, int stopNoPenaltyProgress, int tournamentSize, int childNum, int elites)
{
	popSize = popsize;
	maxGeneration = generationNum;
	stopAfterNoPenaltyProgress = stopNoPenaltyProgress;
	this->tournamentSize = tournamentSize;
	childrenNum = childNum;
	eliteNum = elites;

	ind.reserve(popSize + childrenNum);
	penalty.reserve (popSize + childrenNum);
	//rank.reserve (popSize + childrenNum);
	eliteIndex.reserve(eliteNum);
}

vector<Rectangle> EaToFindRectangles::runAndReturnResult(void)
{
	if (0 == popSize)
	{
		std::cerr << "\nCall EaToFindRectangles::setParams() first.\n"; 
		assert (false && "EA not initialized");
	}
	long int* bestLastPenalty = new long int[stopAfterNoPenaltyProgress];
	for (int i = 0; i < stopAfterNoPenaltyProgress; ++i)
	{
		bestLastPenalty[i] = -1 * i; 
		//we initialize it as 0 for last best, -1 for two last best, etc. 
		//thi way the EA will not stop right away because there has been no progress (all 0s)
	}

	initializeAllToOneBigRectangle();
	//all the population are identical, we do not calculate their penalty multiple times.
	long int onePenalty = EaHelpers::indPenalty(ind[0], majors);
	penalty.resize(popSize);
	std::fill(penalty.begin(), penalty.begin()+popSize, onePenalty);
	int bestLastCounter = 0;
	for (int currentGeneration = 0; currentGeneration < maxGeneration; ++currentGeneration)
	{
		//cout << "\nGeneration " << currentGeneration;
		//the ind vector has popSize elements at this point.
		updateEliteIndexVector();
		//cout << " Best index: " << eliteIndex[0] << " - Best Penalty: " << penalty[eliteIndex[0]];
		//cout << " " << penalty[eliteIndex[0]];
		bestLastPenalty[bestLastCounter] = penalty[eliteIndex[0]];
		++bestLastCounter;
		if (bestLastCounter >= stopAfterNoPenaltyProgress)
		{
			bestLastCounter = 0;
		}

		if ( !EaHelpers::weAreGettingBetter(bestLastPenalty, stopAfterNoPenaltyProgress) )
			break;
		makeChildren();		//this includes updateChildPenaltyes() as well.
		//updateRankVector();
		advancePopulationToNextGen(); //survival. We creat a new vector here.
	}
	delete[] bestLastPenalty;
	return ind[eliteIndex[0]];
}


void EaToFindRectangles::initializeRandom()
{
	throw("Not implemented yet");
}

void EaToFindRectangles::initializeAllToOneBigRectangle()
{
	vector<Rectangle> adam;
	adam.push_back(Rectangle(minors));
	ind.resize(popSize);
	fill(ind.begin(), ind.begin()+popSize, adam);
}

void EaToFindRectangles::updateIndPenalty()
{
	vector<vector<Rectangle>>::const_iterator it = ind.begin();
	for (; it!= ind.begin() + popSize; ++it)
		penalty.push_back(EaHelpers::indPenalty(*it, majors));
}

void EaToFindRectangles::makeChildren()
{
	for (int i = 0; i < childrenNum; ++i)
	{
		vector<int> candidateParentIndex;
		candidateParentIndex.reserve(tournamentSize);
		for (int j = 0; j < tournamentSize; ++j)
		{
			candidateParentIndex.push_back( rand() % (int) popSize);
		}
		int parentIndex = EaHelpers::bestIndIndexAmongCandidates(candidateParentIndex, penalty);
		//insert a copy of the best parent at the end and mutate it in place.
		ind.push_back(ind[parentIndex]);
		mutate(ind.back());
		long int newChildPenalty = EaHelpers::indPenalty(ind.back(), majors);
		penalty.push_back(newChildPenalty);
	}
}

//void EaToFindRectangles::updateRankVector()
//{
//	rank.clear();
//	vector<long int> sortedPenalty(penalty);
//	std::sort(sortedPenalty.begin(), sortedPenalty.end());
//	bool* isSelected = new bool[popSize + childrenNum];
//	for (int i = 0; i < popSize + childrenNum; ++i)
//	{
//		isSelected[i] = false;
//	}
//
//	for (int i = 0; i < popSize + childrenNum; ++i)
//	{
//		int targetLocation = 0;
//		while (targetLocation < popSize + childrenNum && !isSelected[targetLocation] && sortedPenalty[i] != penalty[targetLocation])
//			++targetLocation;
//		if (sortedPenalty[i] == penalty[targetLocation])
//		{
//			isSelected[targetLocation] = true;
//			rank.push_back(targetLocation);
//		}
//		else
//		{
//			cerr << "\nCould not the value I was looking for";
//			assert(false && "EaToFindRectangles::updateRankVector()");
//		}
//	}
//	delete[] isSelected;
//}

void EaToFindRectangles::updateEliteIndexVector()
{
	eliteIndex.clear();
	for (int i = 0; i < eliteNum; ++i)
	{
		eliteIndex.push_back(i);
	}
	EaHelpers::sortEliteIndexVectorBasedOnPenalty(eliteIndex, penalty);
	for (int i = eliteNum; i < popSize; ++i)
	{
		if (penalty[i] < penalty[eliteIndex[eliteNum-1]]) //eliteIndex[eliteNum-1] has the highest penalty in elites.
		{
			eliteIndex[eliteNum-1] = i;
			EaHelpers::sortEliteIndexVectorBasedOnPenalty(eliteIndex, penalty);
		}
	}
}

void EaToFindRectangles::advancePopulationToNextGen()
{
	//we build a new vector of size popSize+childrenNum, and copy 'popSize' number of good individuals
	//(rank proportional selection) to the new array.
	vector<vector<Rectangle>> newPop;
	vector<long int> newPenalty;
	newPop.reserve(popSize);
	newPenalty.reserve(popSize);
	for (int i = 0; i < eliteNum; ++i)
	{
		newPop.push_back(ind[eliteIndex[i]]);
		newPenalty.push_back(penalty[eliteIndex[i]]);
	}
	
	//long int sumPenalty = std::accumulate(penalty.begin(), penalty.begin()+(popSize+childrenNum), 0);
	long int worstPenalty = *(std::max_element(penalty.begin(), penalty.begin()+popSize+childrenNum));

	long int sumFitness = 0;
	for (int i = 1; i < popSize + childrenNum; ++i)
	{
		sumFitness += (worstPenalty - penalty[i]);
	}

	std::uniform_int_distribution<long int> distribution(1,sumFitness);

	for (int i = eliteNum; i < popSize; ++i)
	{
		long int dice = distribution(randomLongGenerator);
		int stopLocation = 0;
		while (dice > 0)
		{
			dice -= (worstPenalty - penalty[stopLocation]);
			++stopLocation;
		}

		--stopLocation; //the previous penalty made it negative.
		newPop.push_back(ind[stopLocation]);
		newPenalty.push_back(penalty[stopLocation]);
	}

	ind.clear();
	penalty.clear();
	ind = newPop;
	penalty = newPenalty;
}

void EaToFindRectangles::mutate(vector<Rectangle>& thisInd)
{
	if ((int) thisInd.size() == 1) //only one rectangle, merge is not possible
	{
		return mutate_splitAny(thisInd);
	}
	if (thisInd.size() == minors.size()) //maximum nomber of rectangles, split is not possible.
	{
		return mutate_mergeTwo(thisInd);
	}

	int mergeProb = (int)(   (double)thisInd.size() * 100.0 / (double)(minors.size())   ); //P(merge) = #of Rectangles / #of minors or irregulars.
	int draw = rand() % 100;
	if (draw <= mergeProb)
	{
		return mutate_mergeTwo(thisInd);
	}
	else
	{
		return mutate_splitAny(thisInd);
	}
}

void EaToFindRectangles::mutate_mergeTwo(vector<Rectangle>& thisInd)
{
	int firstRectIndex = rand() % (int) thisInd.size();
	int secondRectIndex = rand() % ((int) thisInd.size() - 1);
	if (secondRectIndex >= firstRectIndex)
	{
		++secondRectIndex;
	}

	thisInd[firstRectIndex].addRect(thisInd[secondRectIndex]);
	thisInd.erase(thisInd.begin()+secondRectIndex);
}

void EaToFindRectangles::mutate_splitAny(vector<Rectangle>& thisInd)
{
	int splitIndex;
	do
	{
		splitIndex = rand() % (int) thisInd.size();
	}
	while (thisInd[splitIndex].gettotalCoo() <= 1);

	if (thisInd[splitIndex].getBottom() == thisInd[splitIndex].getTop()) //if it's a vertical line
	{
		return mutate_splitThis_vertical(thisInd, splitIndex);
	}
	if (thisInd[splitIndex].getRight() == thisInd[splitIndex].getLeft()) //if it's a vertical line
	{
		return mutate_splitThis_horizontal(thisInd, splitIndex);
	}
	//it's a fat box at this point
	int coin = rand() % 2;
	if (coin == 0)
	{
		return mutate_splitThis_vertical(thisInd, splitIndex);
	}
	else
	{
		return mutate_splitThis_horizontal(thisInd, splitIndex);
	}
}

//		*
//	----------
//		*
void EaToFindRectangles::mutate_splitThis_horizontal(vector<Rectangle>& thisInd, int splitIndex)
{
	if (thisInd[splitIndex].gettotalCoo() < 2 || thisInd[splitIndex].getTop() == thisInd[splitIndex].getBottom())
	{
		cout << "Error - no horizontal split available.";
	}

	Rectangle topRec, bottomRec;
	if (thisInd[splitIndex].gettotalCoo() == 2)
	{
		topRec.addCoo(thisInd[splitIndex].getCoo(0));
		bottomRec.addCoo(thisInd[splitIndex].getCoo(1)); //it really doesn't matter which one is on top of the other
	}

	int splitPoint = rand() % thisInd[splitIndex].gettotalCoo();
	int splitRow = thisInd[splitIndex].getCoo(splitPoint).row;

	for (int i = 0; i < thisInd[splitIndex].gettotalCoo(); ++i)
	{
		if (thisInd[splitIndex].getCoo(i).row <= splitRow)
		{
			bottomRec.addCoo(thisInd[splitIndex].getCoo(i));
		}
		else
		{
			topRec.addCoo(thisInd[splitIndex].getCoo(i));
		}
	}

	if (topRec.gettotalCoo() > 0)
	{
		thisInd[splitIndex] = topRec;
		if (bottomRec.gettotalCoo() > 0)
		{
			thisInd.push_back(bottomRec);
		}
	}
	else
	{
		if (bottomRec.gettotalCoo() > 0)
		{
			thisInd[splitIndex] = bottomRec;
		}
		else
		{
			cerr << "Where the hell did the coos go???";
		}
	}

}

//		|
//	*	|	*
//		|
void EaToFindRectangles::mutate_splitThis_vertical(vector<Rectangle>& thisInd, int splitIndex)
{
	if (thisInd[splitIndex].gettotalCoo() < 2 || thisInd[splitIndex].getLeft() == thisInd[splitIndex].getRight())
	{
		cout << "Error - no vertical split available.";
	}

	Rectangle rightRec, leftRec;
	if (thisInd[splitIndex].gettotalCoo() == 2)
	{
		rightRec.addCoo(thisInd[splitIndex].getCoo(0));
		leftRec.addCoo(thisInd[splitIndex].getCoo(1)); //it really doesn't matter which one is on right of the other
	}

	int splitPoint = rand() % thisInd[splitIndex].gettotalCoo();
	int splitCol = thisInd[splitIndex].getCoo(splitPoint).col;

	for (int i = 0; i < thisInd[splitIndex].gettotalCoo(); ++i)
	{
		if (thisInd[splitIndex].getCoo(i).col <= splitCol)
		{
			rightRec.addCoo(thisInd[splitIndex].getCoo(i));
		}
		else
		{
			leftRec.addCoo(thisInd[splitIndex].getCoo(i));
		}
	}

	if (rightRec.gettotalCoo() > 0)
	{
		thisInd[splitIndex] = rightRec;
		if (leftRec.gettotalCoo() > 0)
		{
			thisInd.push_back(leftRec);
		}
	}
	else
	{
		if (leftRec.gettotalCoo() > 0)
		{
			thisInd[splitIndex] = leftRec;
		}
		else
		{
			cerr << "Where the hell did the coos go???";
		}
	}
}